package array

// 暴力
func MaxSubArrayByMySelf(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	nLength := len(nums)
	left := 0
	max := nums[0]

	for ; left < nLength; left++ {
		total := 0
		for right := left; right < nLength; right++ {
			total += nums[right]
			if total > max {
				max = total
			}
		}
	}
	return max
}

// 动态规划
func MaxSubArray(nums []int) int {
	max := nums[0]

	for i := 1; i < len(nums); i++ {
		if nums[i]+nums[i-1] > nums[i] {
			nums[i] = nums[i] + nums[i-1]
		}
		if nums[i] > max {
			max = nums[i]
		}
	}
	return max
}
